package daily_exercise;


import model.Employee;
import model.ListNode;

import java.util.*;
import java.util.stream.Collectors;

public class Demo5 {


    // 3096. 得到更多分数的最少关卡数目
    public int minimumLevels(int[] possible) {
        // 后缀和
        int n = possible.length;
        int[] postSum = new int[n];
        postSum[n - 2] = possible[n - 1] == 0 ? -1 : 1;
        for (int i = n - 3; i >= 0; i--) {
            postSum[i] = postSum[i + 1] + (possible[i + 1] == 0 ? -1 : 1);
        }

        int sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum += possible[i] == 0 ? -1 : 1;
            if (sum > postSum[i]) return i + 1;
        }
        return -1;
    }



    // 1186. 删除一次得到子数组最大和
    public int maximumSum(int[] arr) {
        // dp[i][0]: 以 i 位置为结尾的子数组中不删除元素,所有元素和的最大值
        // dp[i][1]: 以 i 位置为结尾的子数组中删除一个元素后所有元素的最大值
        int n = arr.length;
        int[][] dp = new int[n][2];

        dp[0][0] = arr[0];
        dp[0][1] = 0;
        int res = arr[0];
        for (int i = 1;  i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
            dp[i][1] = Math.max(dp[i - 1][0], arr[i] + dp[i - 1][1]);
            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
        }
        return res;
    }



    // 2101. 引爆最多的炸弹
    private boolean[] vis;
    private int[] memo;
    private int n;
    private int res;

    public int maximumDetonation(int[][] bombs) {
        n = bombs.length;
        memo = new int[n];

        for (int i = 0; i < n; i++) {
            vis = new boolean[n];
            vis[i] = true;
            res = Math.max(res, bfs(bombs, i));
        }
        return res;
    }

    private int bfs(int[][] bombs, int x) {
        if (memo[x] != 0) return memo[x];

        List<Integer> list = new ArrayList<>();
        list.add(x);
        int index = 0;
        while (index < list.size()) {
            for (int sz = list.size(); index < sz; index++) {
                int pos = list.get(index);
                int tmpSize = list.size();

                for (int i = 0; i < n; i++) {
                    if (i == pos || vis[i]) continue;

                    double distance = calculateDis(bombs, i, pos);
                    if (distance <= Math.pow(bombs[pos][2], 2)) {
                        vis[i] = true;
                        list.add(i);
                    }
                }
                memo[pos] = list.size() - tmpSize;
            }
        }
        return list.size();
    }
    private double calculateDis(int[][] bombs, int i, int j) {
        int xi = bombs[i][0], yi = bombs[i][1];
        int xj = bombs[j][0], yj = bombs[j][1];
        return Math.pow(Math.abs(xi - xj), 2) + Math.pow(Math.abs(yi - yj), 2);
    }



    // 2766. 重新放置石块
    public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        Set<Integer> hash = new HashSet<>();
        for (int x : nums) {
            hash.add(x);
        }

        int n = moveFrom.length;
        for (int i = 0; i < n; i++) {
            hash.remove(moveFrom[i]);
            hash.add(moveTo[i]);
        }

        return hash.stream().sorted((a, b) -> a - b).collect(Collectors.toList());
    }




    // 2844. 生成特殊数字的最少操作
    public int minimumOperations(String num) {
        int n = num.length();
        char[] numArr = num.toCharArray();

        int res = 1000;
        res = Math.min(res, findMinDis('0', '0', numArr));
        res = Math.min(res, findMinDis('2', '5', numArr));
        res = Math.min(res, findMinDis('5', '0', numArr));
        res = Math.min(res, findMinDis('7', '5', numArr));
        return res == 1000 ? n : res;
    }
    private int findMinDis(char left, char right, char[] num) {
        int n = num.length;
        int r = n - 1;
        // 1. 先寻找要求的右边的字符
        while (r >= 0 && num[r] != right) r--;
        if (r < 0) return 1000;
        // 2. 寻找要求的左边的字符
        int l = r - 1;
        while (l >= 0 && num[l] != left) l--;
        if (l < 0) {
            // 做一下特判
            if (right == '0') return n - 1;
            return 1000;
        }
        // 3. 找到符合要求的后缀，返回要删除的字符数量
        return n - l - 2;
    }




    // 2740. 找出分区值
    public int findValueOfPartition(int[] nums) {
        Arrays.sort(nums);
        int res = Integer.MAX_VALUE, n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            res = Math.min(res, nums[i + 1] - nums[i]);
        }
        return res;
    }




    // 3106. 满足距离约束且字典序最小的字符串
    public String getSmallestString(String s, int k) {
        if (k == 0) return s;
        char[] arr = s.toCharArray();
        int n = arr.length, cur = 0;

        for (; cur < n && k > 0; cur++) {
            char ch = arr[cur];
            if (ch == 'a') continue;

            if (ch - 'a' - k <= 0 || ch - 'a' + k >= 26) {
                int count = Math.min(ch - 'a', 26 - (ch - 'a'));
                k -= count;
                arr[cur] = 'a';
            } else {
                arr[cur] = (char)(ch - k);
                break;
            }
        }
        return new String(arr);
    }



    // 682. 棒球比赛
    public int calPoints(String[] operations) {
        List<Integer> list = new ArrayList<>();
        for (String s : operations) {
            char ch = s.charAt(0);
            if (ch == '+') list.add(list.get(list.size() - 1) + list.get(list.size() - 2));
            else if (ch == 'D') list.add(2 * list.get(list.size() - 1));
            else if (ch == 'C') list.remove(list.size() - 1);
            else {
                int num = 0, i = 0;
                if (ch == '-') i++;
                for (; i < s.length(); i++) {
                    num = num * 10 + s.charAt(i) - '0';
                }
                if (ch == '-') num = -num;
                list.add(num);
            }
        }

        int res = 0;
        for (Integer x : list) res += x;
        return res;
    }



    // 2961. 双模幂运算
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0, n = variables.length; i < n; i++) {
            int[] arr = variables[i];
            int a = arr[0], b = arr[1], c = arr[2], m = arr[3];
            if (pow(pow(a, b, 10), c, m) == target) {
                res.add(i);
            }
        }
        return res;
    }
    private int pow (int x, int n, int mod) {
        int res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }




    // 3111. 覆盖所有点的最少矩形数目
    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, (a, b) -> a[0] - b[0]);
        int left = 0, right = 0;
        int res = 1, n = points.length;

        while (right < n) {
            if (points[right][0] - points[left][0] > w) {
                res++;
                left = right;
            }
            right++;
        }
        return res;
    }



    // LCP 40. 心算挑战
    public int maxmiumScore(int[] cards, int cnt) {
        Arrays.sort(cards);

        int n = cards.length;
        int i = n - cnt;
        int res = 0;
        int minOdd = -1, minEven = -1;
        while (i < n) {
            if (cards[i] % 2 == 1 && minOdd == -1) {
                minOdd = cards[i];
            } else if (cards[i] % 2 == 0 && minEven == -1) {
                minEven = cards[i];
            }
            res += cards[i++];
        }
        if (res % 2 == 0) return res;

        // 寻找数组中下标 <= i 的最大奇数，与后 cnt 个数的最小偶数替换
        int j = n - cnt - 1;
        int tmpRes = 0;
        while (j >= 0 && cards[j] % 2 == 0) j--;
        if (j >= 0 && minEven != -1) {
            tmpRes = res - minEven + cards[j];
        }
        // 寻找数组中下标 <= i 的最大偶数，与后 cnt 个数的最小奇数替换
        for (j = n - cnt - 1; j >= 0 && cards[j] % 2 == 1; j--);
        if (j >= 0 && minOdd != -1) {
            tmpRes = Math.max(tmpRes, res - minOdd + cards[j]);
        }

        return tmpRes;
    }



    // 3128. 直角三角形
    public long numberOfRightTriangles(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        // 记录每行和每列值为 1 的格子数
        int[] rows = new int[n], cols = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    rows[i]++;
                    cols[j]++;
                }
            }
        }

        long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    res += (rows[i] - 1) * (cols[j] - 1);
                }
            }
        }
        return res;
    }




    // 572. 另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (root.val == subRoot.val) {
            if (isChildTree(root, subRoot)) return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    private boolean isChildTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val != subRoot.val) return false;
        return isChildTree(root.left, subRoot.left) && isChildTree(root.right, subRoot.right);
    }



    // 3131. 找出与数组相加的整数 I
    public int addedInteger(int[] nums1, int[] nums2) {
        int min1 = 1001, min2 = 1001;
        for (int x : nums1) {
            if (x < min1) min1 = x;
        }
        for (int x : nums2) {
            if (x < min2) min2 = x;
        }
        return min2 - min1;
    }



    // 3132. 找出与数组相加的整数 II
    public static int minimumAddedInteger(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int res = 2000;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int dif = -2000;
                int index = 0, k = 0;
                for (; k < n; k++) {
                    if (k == i || k == j) continue;
                    if (dif != -2000 && nums2[index] - nums1[k] != dif) break;
                    dif = nums2[index++] - nums1[k];
                }
                if (index == m) res = Math.min(res, dif);
            }
        }
        return res;
    }



    // 1035. 不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 最长公共子序列
        int n = nums1.length, m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }



    // 676. 实现一个魔法字典
    class MagicDictionary {
        private Set<String> hash;

        public MagicDictionary() {
            hash = new HashSet<>();
        }

        public void buildDict(String[] dictionary) {
            hash.addAll(Arrays.asList(dictionary));
        }

        public boolean search(String searchWord) {
            char[] word = searchWord.toCharArray();
            for (int i = 0, n = word.length; i < n; i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == word[i]) continue;
                    char tmp = word[i];
                    word[i] = ch;
                    String tmpWord = new String(word);
                    if (hash.contains(tmpWord)) return true;
                    word[i] = tmp;
                }
            }
            return false;
        }
    }

    // 3151. 特殊数组 I
    public boolean isArraySpecial(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] % 2 == nums[i - 1] % 2) return false;
        }
        return true;
    }




    // 3152. 特殊数组 II
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        // dp[i]: 数组nums中以 i 为起点的最长特殊子数组的结束下标
        int n = nums.length, m = queries.length;
        int[] dp = new int[n];
        for (int left = 0, right = 0; right < n; ) {
            if (left == right) dp[left] = right++;
            while (right < n && ((nums[right] ^ nums[right - 1]) & 1) == 1) right++;
            while (left < right) {
                dp[left++] = right - 1;
            }
            left = right;
        }

        boolean[] res = new boolean[m];
        for (int i = 0; i < m; i++) {
            int left = queries[i][0], right = queries[i][1];
            if (dp[left] >= right) res[i] = true;
        }
        return res;
    }



    // 3148. 矩阵中的最大得分
    public int maxScore(List<List<Integer>> grid) {
        int n = grid.size(), m = grid.get(0).size();
        // dp[i + 1][j + 1]: 以(0,0)为左上角，(i,j)为右下角的矩阵，所有元素的最小值
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 0x3f3f3f3f;
        for (int j = 0; j <= m; j++) dp[0][j] = 0x3f3f3f3f;

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = Math.max(res, grid.get(i).get(j) - Math.min(dp[i][j + 1], dp[i + 1][j]));
                dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), grid.get(i).get(j));
            }
        }
        return res;

    }



    // 3137. K 周期字符串需要的最少操作次数
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int n = word.length();
        Map<String,Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i += k) {
            String s = word.substring(i, i + k);
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }

        int count = 0;
        for (String s : hash.keySet()) {
            if (hash.get(s) > count) {
                count = hash.get(s);
            }
        }
        return n / k - count;
    }



    // 551. 学生出勤记录 I
    public boolean checkRecord(String s) {
        int n = s.length();
        int absent = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'A') {
                if (++absent == 2) return false;
            } else if (s.charAt(i) == 'L') {
                int j = i + 1;
                for (; j < n && s.charAt(j) == 'L'; ) j++;
                if (j - i >= 3) return false;
                i = j - 1;
            }
        }
        return true;
    }



    // 3133. 数组最后一个元素的最小值
    public long minEnd(int n, int x) {
        n -= 1;
        long res = x;
        // 从别指向 n 和 x 的比特位（从右向左读）
        int i = 0, j = 0;
        while (n >> i > 0) {
            if ((res >> j & 1) == 0) {
                res |= (long)(n >> i & 1) << j;
                i++;
            }
            j++;
        }
        return res;
    }



    // 3146. 两个字符串的排列差
    public int findPermutationDifference(String s, String t) {
        int res = 0, n = s.length();
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            hash[ch - 'a'] = i;
        }
        for (int i = 0; i < n; i++) {
            char ch = t.charAt(i);
            res += Math.abs(i - hash[ch - 'a']);
        }
        return res;
    }



    private int k, target;
    private int[] buckets;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int n = nums.length, sum = 0;
        for (int x : nums) sum += x;
        if (sum % k != 0) return false;
        target = sum / k;
        // 降序排序，减少递归和回溯次数
        Arrays.sort(nums);
        for (int left = 0, right = n - 1; left <= right; left++, right--) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

        this.buckets = new int[k];
        this.k = k;
        return dfs(nums, 0);
    }
    private boolean dfs(int[] nums, int pos) {
        if (pos == nums.length) return true;

        for (int i = 0; i < k; i++) {
            if (nums[pos] + buckets[i] > target) continue;
            // 两个桶的和一样，那结果一定是相同的，无需进行递归
            if (i > 0 && buckets[i] == buckets[i - 1]) continue;

            buckets[i] += nums[pos];
            if (dfs(nums, pos + 1)) return true;
            buckets[i] -= nums[pos];
        }
        return false;
    }



    // 690. 员工的重要性
//    int res;
//    // 统计各员工是否被访问过
//    boolean[] vis = new boolean[2001];
    // 记录各员工在 employees 中的下标
    int[] employers = new int[2001];

    public int getImportance(List<Employee> employees, int id) {
        for (int i = 0; i < employees.size(); i++) {
            int tmpId = employees.get(i).id;
            employers[tmpId] = i;
        }

        dfs(employees, employers[id]);
        return res;
    }
    private void dfs(List<Employee> employees, int index) {
        res += employees.get(index).importance;
        int id = employees.get(index).id;
        vis[id] = true;

        for (Integer x : employees.get(index).subordinates) {
            if (!vis[x]) {
                dfs(employees, employers[x]);
            }
        }
    }


    // 3153. 所有数对中数位不同之和
    public long sumDigitDifferences(int[] nums) {
        // 统计每个数位上 0 ~ 9 分别有多少个
        int[][] hash = new int[10][10];
        for (int x : nums) {
            int k = 0;
            while (x > 0) {
                hash[k][x % 10]++;
                x /= 10;
                k++;
            }
        }

        long res = 0;
        // 枚举 个位到 十亿位的的情况
        for (int i = 0; i < 10; i++) {
            // 统计该数位上为 0 ~ 9 的和
            int sum = 0;
            for (int j = 0; j < 10; j++) {
                sum += hash[i][j];
            }
            for (int j = 0; j < 10; j++) {
                res += (long)hash[i][j] * (sum - hash[i][j]);
            }
        }
        return res / 2;
    }



    // 3142. 判断矩阵是否满足条件
    public boolean satisfiesConditions(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i + 1 < n && grid[i][j] != grid[i + 1][j]) return false;
                if (j + 1 < m && grid[i][j] == grid[i][j + 1]) return false;
            }
        }
        return true;
    }



    // 3127. 构造相同颜色的正方形
    public boolean canMakeSquare(char[][] grid) {
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                // 记录黑色的格子数
                int sum = 0;
                if (grid[i][j] == 'B') sum++;
                if (grid[i][ j + 1] == 'B') sum++;
                if (grid[i + 1][j] == 'B') sum++;
                if (grid[i + 1][j + 1] == 'B') sum++;
                if (sum != 2) return true;
            }
        }
        return false;
    }



    // 1450. 在既定时间做作业的学生人数
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int res = 0;
        for (int i = 0, n = startTime.length; i < n; i++) {
            if (queryTime >= startTime[i] && queryTime <= endTime[i]) res++;
        }
        return res;
    }



    // 2024. 考试的最大困扰度
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int res = 0;
        res = Math.max(res, computeMaxLen(answerKey, k, 'F'));
        res = Math.max(res, computeMaxLen(answerKey, k, 'T'));
        return res;
    }
    private int computeMaxLen(String answerKey, int k, char falseC) {
        int res = 0;
        int count = k, n = answerKey.length();
        int left = 0, right = 0;
        // 先统计最大的连续‘T’
        while (right < n) {
            // 修改正确答案
            if (answerKey.charAt(right) == falseC) {
                count--;
            }
            // 出窗口
            while (left <= right && count < 0) {
                if (answerKey.charAt(left) == falseC) {
                    count++;
                }
                left++;
            }
            // 统计结果
            res = Math.max(right - left + 1, res);
            right++;
        }
        return res;
    }



    // 2708. 一个小组的最大实力值
    public long maxStrength(int[] nums) {
        // 所有子序列中的最大乘积
        // f[i]: 0 ~ i 位置乘积为正数的子序列的最大乘积
        // g[i]: 0 ~ i 位置乘积为负数的子序列的最大乘积
        int n = nums.length;
        if (n == 1) return nums[0];
        long[] f = new long[n + 1], g = new long[n + 1];

        long res = Long.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            long y = x * f[i - 1], z = x * g[i - 1];
            if (x > 0) {
                f[i] = Math.max(x, Math.max(y, f[i - 1]));
                g[i] = Math.min(g[i - 1], z);
            } else {
                f[i] = Math.max(z, f[i - 1]);
                g[i] = Math.min(x, Math.min(g[i - 1], y));
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }


    // 2860. 让所有学生保持开心的分组方法数
    public int countWays(List<Integer> nums) {
        nums.sort((a, b) -> a - b);

        int res = 1, n = nums.size();
        for (int i = n - 2; i >= 0; i--) {
            // i + 1 必须大于选择学生中的最大值，小于没被选择学生中的最小值
            if (i + 1 > nums.get(i) && i + 1 < nums.get(i + 1)) res++;
        }
        if (nums.get(0) > 0) res++;
        return res;
    }



    // 3174. 清除数字
    public String clearDigits(String s) {
        StringBuilder res = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch >= '0' && ch <= '9' && res.length() > 0) {
                res.deleteCharAt(res.length() - 1);
            } else {
                res.append(ch);
            }
        }
        return res.toString();
    }



    // 977. 有序数组的平方
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1;

        int k = n - 1;
        while (left <= right) {
            int x  = nums[left] * nums[left], y = nums[right] * nums[right];
            if (x >= y) {
                res[k--] = x;
                left++;
            } else {
                res[k--] = y;
                right--;
            }
        }
        return res;
    }



    // 2181. 合并零之间的节点
    public ListNode mergeNodes(ListNode head) {
        ListNode res = new ListNode();
        ListNode tail = res;

        ListNode cur = head;
        while (cur != null) {
            if (cur.val == 0) cur = cur.next;
            if (cur == null) break;

            int sum = 0;
            while (cur != null && cur.val != 0) {
                sum += cur.val;
                cur = cur.next;
            }
            tail.next = new ListNode(sum);
            tail = tail.next;
        }
        return res.next;
    }
}

